package leetcode.code0368;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution4 implements IDebug {

	class Node {
		Node next;
		int seq;
		int val;

		public Node(int seq, int val) {
			this.seq = seq;
			this.val = val;
		}
	}

	public List<Integer> largestDivisibleSubset(int[] nums) {
		Arrays.sort(nums);
		Map<Integer, Node> heads = new HashMap<>();
		Node node = new Node(1, nums[0]);
		heads.put(nums[0], node);
		Node max = node;
		for (int i = 1; i < nums.length; i++) {
			int cur = nums[i];
			Queue<Node> queue = new LinkedList<>();
			Set<Node> replace = new HashSet<>();
			for (Map.Entry<Integer, Node> ahead : heads.entrySet()) {
				Node head = ahead.getValue();
				if (cur % head.val == 0) {
					replace.add(head);
				} else if (head.next != null) {
					queue.add(head.next);
				}
			}
			if (!queue.isEmpty()) {
				Set<Integer> done = new HashSet<>();
				while (!queue.isEmpty()) {
					Node next = queue.poll();
					if (!done.contains(next.val)) {
						done.add(next.val);
						if (cur % next.val == 0) {
							replace.add(next);
						} else if (next.next != null) {
							queue.add(next.next);
						}
					}
				}
			}
			if (replace.size() == 0) {
				node = new Node(1, cur);
				heads.put(cur, node);
			} else {
				int maxSeq = 0;
				Node maxNode = null;
				for (Node rep : replace) {
					if (rep.seq > maxSeq) {
						maxSeq = rep.seq;
						maxNode = rep;
					}
				}
				node = new Node(maxSeq + 1, cur);
				node.next = maxNode;
				heads.remove(maxNode.val);
				heads.put(cur, node);
				if (node.seq > max.seq) {
					max = node;
				}
			}
		}
		List<Integer> ans = new ArrayList<>();
		while (max != null) {
			ans.add(max.val);
			max = max.next;
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<Integer> ans = HelpDebug.str2intlist("[9,18,90,180,360,720]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[5,9,18,54,108,540,90,180,360,720]")));

	}

	@Override
	public void debug2() {
		List<Integer> ans = HelpDebug.str2intlist("[4,8,16]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[3,4,16,8]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		List<Integer> ans = HelpDebug.str2intlist("[2,4,8]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[2,3,4,8]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
